(파이썬 S/W 문제해결 기본) Stack2 - 4874번 4875번 4880번 4881번

4874번 - Forth

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

Forth는 기본 사칙연산 +, -, *, / 4가지만 제공
문제에서 정확하게 어떤 연산자를 제공하는지 명시되었으면 더 좋을 것 같음
정수 나눗셈 연산자 주의!(이거 때문에 오류 찾는 시간이 좀 걸림)

def operator(op, n1, n2): # 나눗셈은 '//' 연산자를 사용해야 하는 것을 주의
return {'+':n1+n2, '-':n1-n2, '*':n1*n2, '/':n1//n2}[op]

def calc_code(code):
stack = []

    for token in code:
        if token == '.':
            if len(stack) == 1:
                return stack.pop()
            # 연산자 수가 부족하여 stack에 숫자가 남은 경우
            else:
                return 'error'

        if token.isdigit():
            stack.append(token)
        else:
            try:
                num2, num1 = int(stack.pop()), int(stack.pop())
                stack.append(operator(token, num1, num2))
            # stack에 계산에 필요한 숫자가 부족한 경우 예외 처리
            except IndexError:
                return 'error'

T = int(input())

for test_case in range(1, T+1): # 연산코드 입력
operation_code = list(input().split())
ans = calc_code(operation_code)

    print('#{} {}'.format(test_case, ans))

---

4875번 - 미로

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

백트래킹을 활용한 미로 탐색

def backtracking(x, y): # 시계방향 (우, 하, 좌, 상)
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
global isPath

    if maze[y][x] == 3:
        isPath = 1
        return

    visited.append((x, y))
    #path.append((x, y))
    for i in range(4):
        nextX = x + dx[i]
        nextY = y + dy[i]

        # 방문하지 않았고, 범위를 벗어나지 않으며, 벽(1)이 아닌 곳
        if (nextX, nextY) not in visited and (0<=nextX<N and 0<=nextY<N) and maze[nextY][nextX] != 1:
            backtracking(nextX, nextY)
            #path.pop()

def findStart():
for y in range(N):
for x in range(N):
if maze[y][x]==2:
return x, y

T = int(input())

for test*case in range(1, T+1): # 미로의 크기
N = int(input())
maze = [[int(num) for num in input()] for * in range(N)]

    # 시작점 찾기
    startX, startY = findStart()

    visited = []
    path = []
    isPath = 0
    backtracking(startX, startY)

    print('#{} {}'.format(test_case, isPath))

---

4880번 - 토너먼트 카드게임

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

이긴 카드의 번호가 아닌 이긴 학생의 번호를 출력해야 함

def winner(left, right):
player1 = card_no[left-1]
player2 = card_no[right-1]
win = ''

    if player1 < player2:
        if player2 == 3 and player1 == 1:
            win = left
        else:
            win = right
    elif player1 > player2:
        if player1 == 3 and player2 == 1:
            win = right
        else:
            win = left
    elif player1 == player2:
        win = left

    return win

def tournament(start, end):
mid = (start+end)//2

    if start == end:
        return start

    left = tournament(start, mid)
    right = tournament(mid+1, end)
    return winner(left, right)

T = int(input())

for test_case in range(1, T+1): # 인원수 입력
N = int(input()) # 카드 입력
card_no = [int(num) for num in input().split()]

    # 절반씩 분할정복하는 재귀호출 함수
    ans = tournament(1, N)

    print('#{} {}'.format(test_case, ans))

---

4881번 - 배열 최소 합

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

n-queen 문제와 비슷

def calc_sum(y):
global sub_sum, min_sum

    if sub_sum > min_sum:
        return

    if y == N:
        if sub_sum < min_sum:
            min_sum = sub_sum
        return

    for x in range(N):
        if not visited[x]:
            visited[x] = True
            sub_sum += array_2d[y][x]
            calc_sum(y+1)
            visited[x] = False
            sub_sum -= array_2d[y][x]

T = int(input())

for test*case in range(1, T+1): # 배열 길이 입력
N = int(input())
array_2d = [[int(num) for num in input().split()] for * in range(N)]

    # 합의 최대
    sub_sum, min_sum = 0, 10*10
    # 방문 체크
    visited = [0] * N
    calc_sum(0)

    print('#{} {}'.format(test_case, min_sum))

---